//
// Created by Administrator on 2021/9/10.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int chalkReplacer(vector<int> &chalk, int k) {
        // 模拟用粉笔这个过程
        int n = static_cast<int>(chalk.size());
        for (int i = 0; i < n; i = (i + 1) % n) {
            k -= chalk[i];
            if (k < 0)
                return i;
        }
        return -1;
        // [1]  1 000 000 000不过  需要优化
    }

    int chalkReplacer2(vector<int> &chalk, int k) {
        // 模拟用粉笔这个过程
        int n = static_cast<int>(chalk.size());
        long long total = accumulate(chalk.begin(), chalk.end(), 0LL);
        // 每一轮的消耗总数是一样的，可以先优化
        k %= total;
        for (int i = 0; i < n; i++) {
            k -= chalk[i];
            if (k < 0)
                return i;
        }
        return -1;
    }

    int chalkReplacer3(vector<int> &chalk, int k) {
        // 遍历chalk的过程可以优化一下 用二分+前缀和
        int n = static_cast<int>(chalk.size());
        if (chalk[0] > k)return 0;
        // 构造前缀和 原位
        for (int i = 1; i < n; ++i) {
            chalk[i] += chalk[i - 1];
            if (chalk[i] > k)
                return i;
        }
        k %= chalk.back(); // 和2一样 先优化
        // 结果是满足 pre[i]>k的最小i
        return upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin();

    }
};

int main() {
    vector<int> chalk{5, 1, 5};
    Solution solution;
    cout << solution.chalkReplacer3(chalk, 22) << endl;
    return 0;
}
